package com.jack.leetcode.eachProblem08;

import java.util.*;

public class 回文对 {

    static Map<String, Integer> indices = new HashMap<>();

    public static List<List<Integer>> palindromePairs(String[] words) {
        int m = words.length;
        List<String> wordList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            wordList.add(new StringBuilder(words[i]).reverse().toString());
        }

        for (int i = 0; i < m; i++) {
            indices.put(wordList.get(i), i);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String tmp = words[i];
            int n = tmp.length();
            if (n == 0) {
                continue;
            }
            for (int j = 0; j <= n; j++) {
                if (isParal(tmp, j, n)) {
                    int leftId = findWord(tmp, 0, j);
                    if (leftId != -1 && leftId != i) {
                        result.add(Arrays.asList(i, leftId));
                    }
                }
                if (j != 0 && isParal(tmp, 0, j)) {
                    int leftId = findWord(tmp, j, n);
                    if (leftId != -1 && leftId != i) {
                        result.add(Arrays.asList(leftId, i));
                    }
                }
            }
        }
        return result;
    }

    private static int findWord(String word, int i, int j) {
        return indices.getOrDefault(word.substring(i, j), -1);
    }

    private static boolean isParal(String word, int i, int j) {
        int len = j - i;
        for (int k = 0; k < len / 2; k++) {
            if (word.charAt(i + k) != word.charAt(j - k - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"abcd", "dcba", "lls", "s", "sssll"};
        palindromePairs(words);
    }
}
